<html>
<head><title>SVDLIBC</title></head>

<body bgcolor="#aaaa9999fffff"> 

<center>
<h1>SVDLIBC</h1>
<h3>A C Library for Computing Singular Value Decompositions</h3>
<h3>version 1.4</h3>
</center>
<hr>

SVDLIBC is a C library written by Doug Rohde.  It was based on the <a
href="http://www.netlib.org/svdpack/">SVDPACKC</a> library, which was written
by Michael Berry, Theresa Do, Gavin O'Brien, Vijay Krishna and Sowmini
Varadhan at the University of Tennessee.  <b>SVDLIBC is made available <a href="license.html">under a BSD License.</a></b>

<p>SVDLIBC offers a cleaned-up version of the code with a new library
interface and a front-end executable that performs matrix file type
conversions, along with computing singular value decompositions.  Currently
the only SVDPACKC algorithm implemented in SVDLIBC is
<b>las2</b>, because it seems to be consistently the fastest.  This algorithm
has the drawback that the low order singular values may be relatively
imprecise, but that is not a problem for most users who only want the
higher-order values or who can tolerate some imprecision.
<p>

<h3>Installing</h3>

To install SVDLIBC:

<ol>
<li><a href="svdlibc.tgz">Click here to download the tar file.</a>
<li>To unpack the tar file run this on the command-line:<br>
<b>tar xvzf svdlibc.tgz<br>
cd SVDLIBC</b>
<li>You may want to edit the Makefile to use your favorite compiler.
<li>Run <b>make</b>.
</ol>

This will build the <b>libsvd.a</b> library, located in a directory whose name
is based on your HOSTTYPE environment variable (note that some shells don't
have that set properly by default).  This allows compilation for different
architectures on a shared file system.  It will also create the command-line
interface executable, called <b>svd</b>.

<h3>Command-line Interface</h3>

The command-line interface, <b>svd</b>, allows you to perform an SVD on a
matrix, optionally storing the left- and right-singular vectors and the
singular values in separate files.  You can also use it to convert from one
matrix file format to another.
<p>
Note that the SVDPACKC matrix file formats are designed to be simple and do
not include magic cookies or have conventional extensions to allow the format
to be determined automatically.  Therefore, you may need to use the -r and -w
options to specify the input and output formats.
<p>

<table border=2>
<tr><th colspan=3>Usage
<tr><td colspan=3>svd [options] matrix_file

<tr><td>-a<td><i>algorithm</i>
<td>Set the algorithm to use.  They include:<br>
<table>
<tr><td width=30>las2<td>Single-Vector Lanczos Method (default)
</table>

<tr><td>-c<td><i>infile outfile</i>
<td>Converts a matrix file to a new format (using -r and -w to specify the old
and new formats).  Then exits immediately.

<tr><td>-d<td><i>dimensions</i>
<td>Desired number of SVD triples or dimensions (default is all)

<tr><td>-e<td><i>bound</i>
<td>Minimum magnitude of wanted eigenvalues for las2 (1e-30)

<tr><td>-k<td><i>kappa</i>
<td>Accuracy parameter for las2 (1e-6)

<tr><td>-i<td><i>iterations</i>
<td>Maximum algorithm settling iterations.  By default it iterates as many
times as necessary to obtain the desired number of dimensions, and most users
will not want to adjust this.  But you can set this to a lower value to speed
things up, with the possible loss of some dimensions.

<tr><td>-o<td><i>file_root</i>
<td>Root of files in which to store resulting U', S, and V'

<tr><td>-r<td><i>format</i>
<td>Input matrix file format (see below for <a href="#formats">format specifications</a>)<br>
<table>
<tr><td width=30>       st     <td>   Sparse text (default)
<tr><td>       sth    <td>   SVDPACK Harwell-Boeing text format
<tr><td>       dt     <td>   Dense text
<tr><td>       sb     <td>   Sparse binary
<tr><td>       db     <td>   Dense binary
</table>

<tr><td>-t<td>
<td> Transposes the input matrix.  Can be used when computing the SVD or
converting the format with -c.

<tr><td>-v<td><i>verbosity</i>
<td> Default is 1.  Use 0 for no feedback, 2 to list singular values, and 3 for
the vectors too.

<tr><td>-w<td><i>format</i>
<td> Output matrix file format.  Options are same as for -r, but default is
dense text.<br>
</table>

<p>
If the -o option is used, the resulting U' and V' matrices will be stored in
files whose name is the specified file_root with "-Ut" or "-Vt" appended to
the end.  The matrices stored in these files are actually the transposes of
the traditionally defined U and V matrices, so that the rows of the "-Ut"
matrix are the left singular vectors and the rows of the "-Vt" matrix are the
right singular vectors, which is generally more convenient.  The "-S" file
contains an array of the singular values, the first line of which holds the
number of values.


<h3>C Library Interface</h3>

The interface to the SVDLIBC library is defined in <a
href="svdlib.h">svdlib.h</a>, which should be fairly self-explanatory.
<p>
The library defines three structures.  An <tt>SMat</tt> is a pointer to a
<tt>struct smat</tt>, which is a sparse matrix.  A <tt>DMat</tt> is a pointer
to a <tt>struct dmat</tt>, which holds a dense matrix.  Finally, a
<tt>SVDRec</tt> is a pointer to a <tt>struct svdrec</tt>, which holds the
results of an SVD: the dimensionality (d), the left- and right- singular
matrices (Ut and Vt), and <a href="#formats">file types</a> (such as SVD_F_ST).
Any file type can be loaded to or written from either a sparse or dense
matrix.
<p>
Finally, the <tt>svdLAS2</tt> function actually computes the SVD.  It takes a
sparse matrix and some parameters and returns an SVDRec containing the
components of the SVD. <tt>svdLAS2A</tt> is a simpler version that attempts to
automatically choose reasonable parameter values and requires only a matrix
and the desired number of dimensions (or 0 for all).


<h3>Matrix File Formats</h3>
<a name="formats">

The sparse formats are more efficient for sparse matrices, the dense ones for
dense matrices.  The binary formats will be faster to read and write and will
be smaller if the matrix uses high-precision floating point numbers.  Values
are stored in 4-byte floats, not in 8-byte doubles.
<p>
<table border=2>
<tr>
<th>Library<br>
Code
<th>Command-line<br>
Code
<th>Description
<tr>
<td>SVD_F_ST
<td>st
<td><a href="SVD_F_ST.html">Sparse matrix, text format.</a>

<tr>
<td>SVD_F_STH
<td>sth
<td><a href="SVD_F_STH.html">Sparse matrix, Harwell-Boeing text format used in 
SVDPACKC.</a>

<tr>
<td>SVD_F_SB
<td>sb
<td><a href="SVD_F_SB.html">Sparse matrix, binary format.</a>

<tr>
<td>SVD_F_DT
<td>dt
<td><a href="SVD_F_DT.html">Dense matrix, text format.</a>

<tr>
<td>SVD_F_DB
<td>db
<td><a href="SVD_F_DB.html">Dense matrix, binary format.</a>

</table>

<h3>Version Notes</h3>

<table>
<tr><td valign=top><b>1.4</b>
<td><ul>
<li> Added BSD License
<li> Incorporated bug fixes by piskvorky, <a href="https://github.com/lucasmaystre/svdlibc/commit/9d0f04b32f6e4c806f2b51127e846bdee8d24f42">reported here</a>.
<li> Fixed some gcc compiler warnings.
</ul>

<tr><td valign=top><b>1.34</b>
<td><ul>
<li> Worked around a gcc optimizer bug that was reordering statements in the
initial precision calculations, resulting in bad computations on some Linux
machines.
<li> Fixed some g++ compiler warnings.
<li> Fixed the icc compiler flags for Linux machines.
</ul>

<tr><td valign=top><b>1.33</b>
<td><ul>
<li> Fixed a numeric overflow problem in the matrix validation which caused
errors for high-dimensional matrices.
</ul>

<tr><td valign=top><b>1.32</b>
<td><ul>
<li> Upgraded the Harwell-Boeing input and output file formats to better
support the spec.  Files output in this format by version 1.32 or later may
not be readable by earlier versions of the library.
</ul>

<tr><td valign=top><b>1.31</b>
<td><ul>
<li> Fixed type errors that caused problems on AIX systems.
</ul>

<tr><td valign=top><b>1.3</b>
<td><ul>
<li> Removed the need to specify the number of iterations.  It should now use
less memory and always get the correct answer if the number of iterations is
not given.
<li> Removed a bug that prevented obtaining just 1 or 2 dimensions.
<li> The -t option was added to allow matrix transposition, which is done
efficiently for sparse matrices.
<li> Matrices with significantly more columns than rows will be transformed
before the SVD is computed to improve the speed.
</ul>

<tr><td valign=top><b>1.21</b>
<td><ul>
<li> Fixed a bug that caused segmentation faults when the number of iterations
was as large as the matrix size.
</ul>

<tr><td valign=top><b>1.2</b>
<td><ul>
<li> The memory usage has been reduced, allowing svdLAS2() to handle larger matrices.
</ul>

<tr><td valign=top><b>1.1</b>
<td><ul>
<li> The svdLAS2A() function has been added.
<li> The second and third arguments to svdLAS2() have been swapped so
dimensions comes before iterations.
<li> Renamed internal functions to prevent linker conflicts with the <a
href="../DRUtils">DRUtils</a> library.
</ul>

<tr><td valign=top><b>1.01</b>
<td><ul>
<li> Fixed a bug (which exists in SVDPACKC) that produced incorrect results in
matrices with less than full rank.  Thanks to Greg Landrum for pointing out
this problem.
</ul>

<tr><td valign=top><b>1.0</b>
<td><ul>
<li> The first one.
</ul>
</table>

<h3>Feedback</h3>
Comments, questions, and bug reports should be addressed to <a
href="mailto:dr+svd@tedlab.mit.edu">dr+svd@tedlab.mit.edu</a>.
<p>
<hr>
<address>
Doug Rohde, <a href="mailto:dr+svd@tedlab.mit.edu">dr+svd@tedlab.mit.edu</a>,<br>
Department of Brain and Cognitive Science,<br>
<a href="http://web.mit.edu">Massachusetts Institute of Technology</a>
</address>
</body>
